
\section{Related Work}
%The problem of Web-scale instance matching has only been studied recently, while most of the work so far focused on the single domain context. 

%We will now briefly discuss existing work 
%along the main dimensions of attributes (or \emph{features} in general), \emph{similarity measures} and \emph{matching techniques}. Also, we will present the main directions towards \emph{Web-scale integration} and position our contributions along this line. 

%\subsection{Matching Features}
Instances are similar, thus, are considered candidate matches if their \emph{features} are similar \cite{fellegi_theory_1969}. 
%A great variety of features have been employed 
%in order to solve this instance matching problem, 
%while instances in different settings, may be represented as different types of database records or RDF resources. Traditionally, 
Features used are derived from flat attributes, structure information of instances (e.g. relations between RDF resources)~\cite{melnik_similarity_2002,spaccapietra_survey_2005} or semantic information. 
%For instance, ObjectCoref \cite{hu_bootstrapping_2011} considers resources as matches if their discriminative attributes are similar. 
%The discriminativeness is inferred from attribute characteristics captured by semantic constraints
%expressed using the Web Ontology Language, OWL), including 
%such as 
%\verb+owl:InverseFunctionalProperty+, 
%\verb+owl:FunctionalProperty+ and \verb+owl:cardinality+. 
While we focus on the use of flat attribute values in the experiment, SERIMI is also applicable to other features. 

%\subsection{Similarity Measures}
Instance matching using flat features typically relies on string comparison using different \emph{similarity metrics}. 
%Character-based metrics (e.g. Jaro, Q-grams), 
% work well for detecting typographical errors. 
%token-based metrics (e.g., SoftTF-IDF, Jaccard) and 
%work well when features have many words and the arrangement of words cannot be captured by character-based metrics (e.g., ``Michael Jackson'' vs. ``Jackson, Michael''), 
%document-based similarity metrics (e.g., cosine similarity) 
%are employed when the number of tokens to be compared is large. 
%and phonetic metrics (e.g., Soundex) can deal with features that are phonetically similar. 
%, but are not at the level of character or token. 
%Numeric metrics were designed to capture the nuances of numeric features. 
%are the types which consider strings as features. Besides these string-based metrics, 
%are not able to detect similarity between synonyms, nicknames, abbreviations and acronyms (e.g, ``Big Apple'' and ``New York''). To address this, 
%there are also lexical semantic relatedness metrics \cite{han_structural_2010,budanitsky_evaluating_2006} which leverage semantic information from general knowledge sources (e.g., Wikipedia) or lexical sources (e.g., WordNet).  
Although there are many similarity metrics, there is no single one that applies in all cases \cite{cohen_comparison_2003}. 
%Different features have different characteristics that demand different metrics. Some authors propose that the best way to approach this problem is by 
Learning the right metrics for the given features, and combining different metrics \cite{branting_comparative_2003} are the best strategies. Which metrics to be used is also not the focus here, where we simply employ a string-based metric for the experiment. 

%\subsection{Matching Techniques}
Orthogonal to features and metrics, different \emph{matching techniques} have been proposed to address both the efficiency and effectiveness of instance matching. \emph{Data blocking techniques} \cite{hernandez_merge/purge_1995} aims to make it more efficient by reducing the number of unnecessary comparisons between records. Based on a feature that is distinctive 
%and can be processed efficiently
(also called Blocking Key Value, BKV), instances are partitioned into blocks such that potentially similar instances (i.e. candidate results to be further refined) are placed in the same block~\cite{hernandez_merge/purge_1995,mccallum_efficient_2000}. 
%Each block can be considered as a set of candidate matches, which subsequently are disambiguated through a more sophisticated and effective method. 
%Examples of blocking techniques include the sorted neighborhood approach  and canopy clustering \cite{mccallum_efficient_2000}. 
Recently, an unsupervised blocking technique has been explicitly proposed for the heterogeneous Web setting, where the BKV is simply the set of all tokens that can be extracted from the instance data~\cite{papadakis_efficient_2011}. Silks~\cite{DBLP:conf/webdb/IseleJB11} is another solution for this setting, which however, requires a manual identification of the BKV. 
%This approach differs from the single-domain techniques in that instead of using specific attributes, it simply uses tokens from all attributes. Thus, it can deal with multiple domains and schemas because instances to be compared do not have to share common attributes (i.e. their schemas are not assumed to be same or pre-aligned).

There are two major kinds of approaches that target the effectiveness of matching. Usually, they are employed after blocking for the disambiguation of candidate matches. There are \emph{learning-based approaches} that can be further distinguished in terms of training data and degree of supervision, respectively (i.e. supervised, semi-supervised, unsupervised \cite{bernstein_discovering_2009,Song:2011:AGD:2063016.2063058,Niu:2011:ZWC:2063076.2063091}). ObjectCoref is a supervised approach that self-learns the discriminativeness of RDF properties. Then, matches are computed based on comparing values of a few discriminative properties. RIMON is an unsupervised approach that firstly applies blocking to produce a set of candidate resources and then, uses a document-based similarity metric (cosine similarity) for disambiguating candidate resources. 
%As features, it models
%%goes beyond flat attributes to 
%an instance as a vector of terms that are extracted from the structure formed by the instance and its neighbors. 
\emph{Collective matching} represents the other kind of approach \cite{spaccapietra_survey_2005}. It exploits the intuition that two instances are similar if their neighbours are similar. Similarity flooding \cite{melnik_similarity_2002} is a generic graph-matching algorithm that implements this intuition. 
%This algorithm was adopted to the LDW setting to deal with ontology matching \cite{wang_structure-based_2010}. 

%\subsection{Instance matching on the Web}
%Recently, different directions towards \emph{Web-scale matching} have been pursued. One prominent concept is pay-as-you-go data integration \cite{das_sarma_bootstrapping_2008}, which recognizes that in large-scale scenarios, it is not affordable to perform integration completely upfront but rather, it shall be considered as a continuous process. 
% that involves users, where integration results are incrementally obtained and refined as the system evolves. 
%In particular, Google researchers have studied keyword search-based data integration, where matching tasks are carried out during user search activities \cite{DBLP:conf/sigmod/TalukdarIP10}. Besides these general concepts, a few technical solutions have also been proposed to deal with schema and ontology matching \cite{budanitsky_evaluating_2006} in the LDW context. However, 
%Besides the works
%% the blocking technique \cite{papadakis_efficient_2011} and the two preliminary works, ObjectCoref and RIMON, 
%mentioned above, there exists no effective solution for the instance-matching problem in the multiple domains and schemas. 

%We target this problem setting, providing an unsupervised approach that can be used in combination with existing blocking techniques \cite{papadakis_efficient_2011} to disambiguate candidate matches. 
%%That is, we focus on the effectiveness of matching, aiming at refining candidate results previously obtained through a simple but efficient blocking technique. 
%As opposed to previous works \dtr{cite}, which are based on \emph{direct matching} of instances between the source and the target datasets based on some common attributes, the disambiguation involves only instances of the same target dataset. 
%%To the best of our knowledge, 
%%this is the first approach that 
%This enables the effective matching of instances across domains and possibly non-overlapping schemas. 